package com.shawn.datastructure.heap;

/**
 * 堆
 * @author com.shawn
 */
public class Heap {

	/**
	 * 数组，从下标为1开始存储数据
	 */
	private int[] data;
	/**
	 * 堆可以存储的最大数据个数
	 */
	private int capacity;
	/**
	 * 堆中已经存储的数据个数
	 */
	private int size;

	public Heap(int capacity) {
		data = new int[capacity + 1];
		this.capacity = capacity;
		size = 0;
	}

	public void insert(int value) {
		// 堆满
		if (size >= capacity) {
			return;
		}
		++size;
		data[size] = value;
		int i = size;
		// 自下往上堆化
		while (i / 2 > 0 && data[i] > data[i / 2]) {
			swap(data, i, i / 2);
			i = i / 2;
		}
	}

	public void removeMax() {
		if (size == 0) {
			// 堆中没有数据
			return;
		}
		data[1] = data[size];
		--size;
		heapify(data, size, 1);
	}

	/**
	 * @param a 数组 a 中的数据从下标 1 到 n 的位置
	 * @param n 表示数据的个数
	 */
	public void sort(int[] a, int n) {
		buildHeap(a, n);
		int k = n;
		while (k > 1) {
			swap(a, 1, k);
			--k;
			heapify(a, k, 1);
		}
	}

	private void buildHeap(int[] a, int n) {
		for (int i = n / 2; i >= 1; --i) {
			heapify(a, n, i);
		}
	}

	/**
	 * 自上往下堆化
	 *
	 * @param arr
	 * @param n
	 * @param i
	 */
	private void heapify(int[] arr, int n, int i) {
		while (true) {
			int maxPos = i;
			if (i * 2 <= n && arr[i] < arr[i * 2]) {
				maxPos = i * 2;
			}
			if (i * 2 + 1 <= n && arr[maxPos] < arr[i * 2 + 1]) {
				maxPos = i * 2 + 1;
			}
			if (maxPos == i) {
				break;
			}
			swap(arr, i, maxPos);
			i = maxPos;
		}
	}

	private void swap(int[] arr, int p, int q) {
		int temp = arr[p];
		arr[p] = arr[q];
		arr[q] = temp;
	}

}
